package class07;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: https://leetcode.com/problems/path-sum-ii/
 * @time: 2021/7/17 13:52
 * @author: lhy
 */
public class PathSumII {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> path = new ArrayList<>();
        process(root, path, 0, targetSum, ans);
        return ans;
    }

    private void process(TreeNode root, List<Integer> path, int preSum, int targetSum, List<List<Integer>> ans) {
        if (root.left == null && root.right == null) {
            if (preSum + root.val == targetSum) {
                path.add(root.val);
                ans.add(copy(path));
                path.remove(path.size() - 1);
            }
        }
        path.add(root.val);
        preSum += root.val;
        if (root.left != null) {
            process(root.left,path,preSum,targetSum,ans);
        }
        if (root.right != null) {
            process(root.right,path,preSum,targetSum,ans);
        }
        path.remove(path.size() - 1);
    }

    private List<Integer> copy(List<Integer> path) {
        return new ArrayList<>(path);
    }

}
